#ifndef _defs_h_
#include "defs.h"
#define _defs_h_
#endif

class BinaryTree
{
protected:
	KnightTree* pRoot;
public:
	BinaryTree();
	void getRoot(KnightTree* &);	
	void BST_recur(KnightTree* &, int, int);
	void insertBST(int , int);
	KnightTree* findNode(int);
	void compare_recur(KnightTree* , KnightTree* &, int);
	void deleteNode(KnightTree* &);
	void delete_recur(KnightTree* &, KnightTree* &);
	bool isEmpty();
	void newInserting(int, int);
	void removeNode(KnightTree* &);
	void LNR_recur(KnightTree*, KnightTree* &);
	void ultiDauBo(int);
	void DauBoDepTrai(KnightTree* &, int &, int);
	int depth(KnightTree*);
	int tinhSoLa(KnightTree* , int);
	int SoLa();
	int tinhSoNut_recur(KnightTree*);
	int tinhSoNut();
	int tinhDoCao_recur(KnightTree*);
	int DoCao();
	//----
	void rotateLeft(KnightTree*& );
	void rotateRight(KnightTree*&);
	void rotateLeftTwice(KnightTree*&);
	void rotateRightTwice(KnightTree*&);
	//----
	KnightTree *insertAVL_recur(KnightTree* &, int, int);
	void insertAVL(int, int);

};

BinaryTree::BinaryTree()
{
	pRoot = NULL;
}

void BinaryTree::getRoot(KnightTree* &pReturn)
{
	pReturn = pRoot;
}

void BinaryTree::BST_recur(KnightTree* &pNode, int key, int level)
{
	if (pNode == NULL)
	{
		KnightTree* newNode = new KnightTree();
		newNode->key = key;
		newNode->level = level;
		newNode->pLeftChild = NULL;
		newNode->pRightChild = NULL;
		pNode = newNode;
	}
	else 
	{
		if(key < pNode->key)
			BST_recur(pNode->pLeftChild, key, level);
		else
		{
			if(key == pNode->key)
			{
				if(key == 998);
				else
				{
					key++;
					if(key == 888)
						key++;
					BST_recur(pNode->pRightChild, key, level);
				}
			}
			else BST_recur(pNode->pRightChild, key, level);
		}
	}
}

void BinaryTree::insertBST(int key, int level)
{
	BST_recur(pRoot, key, level);
}

void BinaryTree::compare_recur(KnightTree* pNode, KnightTree* &nearestNode, int key2)
{
	if(pNode != NULL)
	{
		compare_recur(pNode->pLeftChild, nearestNode, key2);
		int abs_pRootNode = (pNode->key > key2)? (pNode->key - key2) : (key2 - pNode->key);
		int abs_pHiepSi = (nearestNode->key > key2)? (nearestNode->key - key2) : (key2 - nearestNode->key);
		if((abs_pRootNode < abs_pHiepSi) || ((abs_pRootNode == abs_pHiepSi) && (pNode->key < nearestNode->key)))
			nearestNode = pNode;
		compare_recur(pNode->pRightChild, nearestNode, key2);
	}
}

KnightTree* BinaryTree::findNode(int key)
{
	KnightTree* nearestNode = pRoot;
	compare_recur(pRoot, nearestNode, key);
	return nearestNode;
}

void BinaryTree::deleteNode(KnightTree* &pTemp)
{
	delete_recur(pRoot, pTemp);
}

void BinaryTree::delete_recur(KnightTree* &rootNode, KnightTree* &deleteNode)
{
	if (rootNode != NULL)
	{
		if (rootNode->key < deleteNode->key)
			delete_recur(rootNode->pRightChild, deleteNode);
		else if (rootNode->key > deleteNode->key)
			delete_recur(rootNode->pLeftChild, deleteNode);
		else
		{
			if (rootNode->pLeftChild == NULL && rootNode->pRightChild == NULL)
				rootNode = NULL;
			else if (rootNode->pLeftChild == NULL)
			{
				rootNode = rootNode->pRightChild;
				delete deleteNode;
			}
			else if (rootNode->pRightChild == NULL)
			{
				rootNode = rootNode->pLeftChild;
				delete deleteNode;
			}
			else
			{
				KnightTree* pNewRoot = rootNode->pRightChild;
				KnightTree* pParent = rootNode->pRightChild;
				if (pNewRoot->pLeftChild != NULL)
				{
					while (pNewRoot->pLeftChild != NULL)
					{
						pParent = pNewRoot;
						pNewRoot = pNewRoot->pLeftChild;
					}
					pParent->pLeftChild = pNewRoot->pRightChild;
					pNewRoot->pRightChild = rootNode->pRightChild;
				}
				pNewRoot->pLeftChild = rootNode->pLeftChild;
				pRoot = pNewRoot;
				delete deleteNode;
			}
		}
	}
}

bool BinaryTree::isEmpty()
{
	if(pRoot == NULL)
		return 0;
	else return 1;
}

void BinaryTree::LNR_recur(KnightTree* pNode, KnightTree* &newNode)
{
	if(pNode != NULL)
	{
		LNR_recur(pNode->pLeftChild, newNode);
		BST_recur(newNode, pNode->key, pNode->level);
		LNR_recur(pNode->pRightChild, newNode);
	}
}

void BinaryTree::removeNode(KnightTree* &a)
{
	if(a != NULL)
	{
		removeNode(a->pLeftChild);
		removeNode(a->pRightChild);
		KnightTree* tmp = a;
		a = NULL;
		delete tmp;
	}
}

void BinaryTree::newInserting(int key, int level)
{
	KnightTree* newRoot = new KnightTree();
	newRoot->key = key;
    newRoot->level = level;
	newRoot->pLeftChild = NULL;
    newRoot->pRightChild = NULL;
	
	LNR_recur(pRoot, newRoot);
	KnightTree* pTempRoot = pRoot;
	pRoot = newRoot;
	removeNode(pTempRoot);
}

void BinaryTree::ultiDauBo(int level)
{
	int DoSauCay = depth(pRoot); 
	DauBoDepTrai(pRoot, DoSauCay, level);
}

void BinaryTree::DauBoDepTrai(KnightTree *&pNodeRoot,int &DoSau, int level)
{
	if(pNodeRoot != NULL && DoSau >= level)
	{
		DauBoDepTrai(pNodeRoot->pLeftChild, DoSau, level);
		DauBoDepTrai(pNodeRoot->pRightChild, DoSau, level);
		KnightTree* pDlt = pNodeRoot;
		pNodeRoot = NULL;
		delete pDlt;
		DoSau--;
	}
}

int BinaryTree::depth(KnightTree *pRootNode)
{
	if (pRootNode == NULL) 
		return 0;
    int left = depth(pRootNode->pLeftChild);  
    int right = depth(pRootNode->pRightChild);
    return (left > right)? (left+1) : (right+1);
}

int BinaryTree::tinhSoLa(KnightTree* pRootNode, int tong)
{
	if(pRootNode->pLeftChild == NULL && pRootNode->pRightChild == NULL)
			tong++;
	if(pRootNode->pLeftChild != NULL)
	{
		tinhSoLa(pRootNode->pLeftChild,tong);
	}
	if(pRootNode->pRightChild != NULL)
	{
		tinhSoLa(pRootNode->pRightChild, tong);
	}
}

int BinaryTree::SoLa()
{
	int TongSoLa = 0;
	tinhSoLa(pRoot,TongSoLa);
	return TongSoLa;
}

int BinaryTree::tinhSoNut_recur(KnightTree* pRootNode)
{
    if(pRootNode == NULL)
		return 0;
	return(tinhSoNut_recur(pRootNode->pLeftChild)+1+tinhSoNut_recur(pRootNode->pRightChild));
}

int BinaryTree::tinhSoNut()
{
	int sonut = 0;
	sonut = tinhSoNut_recur(pRoot);
	return sonut;
}

int BinaryTree::tinhDoCao_recur(KnightTree* pRoot)
{
	if(pRoot == NULL)
		return 0;
	int l=tinhDoCao_recur(pRoot->pLeftChild);
	int r=tinhDoCao_recur(pRoot->pRightChild);
	if(l > r)
		return l+1;
	else
		return r+1;
}

int BinaryTree::DoCao()
{
	int docao = 0;
	docao = tinhDoCao_recur(pRoot);
	return docao;
}

KnightTree* BinaryTree::insertAVL_recur(KnightTree* &rootNode, int key, int level)
{
	if (rootNode == NULL)
	{
		KnightTree *newNode = new KnightTree();
		newNode->level = level;
		newNode->key = key;
		newNode->pLeftChild = NULL;
		newNode->pRightChild = NULL;
		rootNode = newNode;
	}
	else if (key < rootNode->key)
	{
		insertAVL_recur(rootNode->pLeftChild, level, key);
		if (tinhDoCao_recur(rootNode->pLeftChild) - tinhDoCao_recur(rootNode->pRightChild) == 2)
		{
			if (key < rootNode->pLeftChild->key)
				rotateLeft(rootNode);
			else
				rotateLeftTwice(rootNode);
		}
	}
	else if (key>rootNode->key)
	{
		insertAVL_recur(rootNode->pRightChild, level, key);
		if (tinhDoCao_recur(rootNode->pRightChild) - tinhDoCao_recur(rootNode->pLeftChild) == 2)
		{
			if (key > rootNode->pRightChild->key)
				rotateRight(rootNode);
			else
				rotateRightTwice(rootNode);
		}
	}
	return rootNode;		 
}
//-----
void BinaryTree::rotateLeft(KnightTree*& rootNode)
{
	KnightTree *otherNode;
	otherNode = rootNode->pLeftChild;
	rootNode->pLeftChild= otherNode->pRightChild;
	otherNode->pRightChild = rootNode;
	rootNode = otherNode;
}
void BinaryTree::rotateRight(KnightTree*& rootNode)
{
	KnightTree *otherNode;
	otherNode = rootNode->pRightChild;
	rootNode->pRightChild = otherNode->pLeftChild;
	otherNode->pLeftChild = rootNode;
	rootNode = otherNode;
}
void BinaryTree::rotateLeftTwice(KnightTree* &rootNode)
{
	rotateRight(rootNode->pLeftChild);
	rotateLeft(rootNode);
}
void BinaryTree::rotateRightTwice(KnightTree* &rootNode)
{
	rotateLeft(rootNode->pRightChild);
	rotateRight(rootNode);
}
//------
void BinaryTree::insertAVL(int key, int level)
{
	insertAVL_recur(pRoot, key, level);
}



//--------------------------------------------------------------
KnightTree*  siege(eventList* pEvent)
{
	KnightTree* pTree = NULL;
	//let's save the lady here
	eventList* &tmp = pEvent;
	KnightTree* nearestNode = NULL;
	KnightTree* pRoot = NULL;
	bool end = 0;
	bool robinhood = 0;
	int key = 0;
	int level = 0;
	int nLevel = 0;
	bool DauBo = 0;
	int lvRobinhood = 0;
	bool loop = 0;
	bool darkknight = 0;
	//Khai bao bien
	BinaryTree* BSTree = new BinaryTree();
//-----------------------------------------------------------------------
	while(tmp != NULL)
	{
		if(pEvent->nEventCode > 10000 && pEvent->nEventCode < 19999) //case 1 hiep si 
		{
			key = (pEvent->nEventCode - 10000)/10;     
			level = (pEvent->nEventCode - 10000)%10;

			if(key == 777 && darkknight == 0) 
			{
				robinhood = 1;
				lvRobinhood = level;			
				BSTree->newInserting(key, level);
			}
			else if (key == 000)  // GWS
			{
				if (BSTree->tinhSoNut() == ((2*BSTree->DoCao() )- 1));
				else 
				{
					BSTree->insertBST(key, level);
				}
				
			}
			else if(key == 999) // darknight
			{
				robinhood = 0;
				darkknight = 1;
				BSTree->insertAVL(key, level);
			}
			else 
			{
				BSTree->insertBST(key, level);
			}
		}
//-----------------------------------------------------------------------------case 2 rowena 
		else if (pEvent->nEventCode > 2000 && pEvent->nEventCode < 2900)
		{
			key = pEvent->nEventCode - 2000;
			nearestNode = BSTree->findNode(key);
			if(nearestNode->level < 9)
				nearestNode->level++;
		}
//-----------------------------------------------------------------------------case - ve si giu thanh
		else if(pEvent->nEventCode < 0)
		{
			key = -(pEvent->nEventCode/10);  
			level = -(pEvent->nEventCode%10);

			if (key == 888) // DBG
			{
				loop = 1;
				{
				nearestNode = BSTree->findNode(key);
				if(nearestNode->level >= level)
				{
					loop = 0;
				}
				else BSTree->deleteNode(nearestNode);
				if(BSTree->isEmpty() == 0)
				{
					return NULL;
				}
				}
			}

			else if (key == 777) // DauBo
			{
				if(robinhood == 1 && lvRobinhood == level)
					;
				else
				{
					if(BSTree->SoLa() == nLevel)
					{
						BSTree->ultiDauBo(level);
						if(BSTree->isEmpty() == 0)
						{
							return NULL;
						}
					}
				
						else 
					{
						nearestNode = BSTree->findNode(key);
						if(nearestNode->level >= level);
						else BSTree->deleteNode(nearestNode);
						if(BSTree->isEmpty() == 0)
						{
							return NULL; 
						}
					}
				}
			}

			else
			{
				nearestNode = BSTree->findNode(key);
				if(nearestNode->level >= level)
				{
					if (key == 888)
						loop = 0;
				}
				else 
				{
					BSTree->deleteNode(nearestNode);
					
				}
				if(BSTree->isEmpty() == 0)
				{
					return NULL; 
				}
			}

		}
//-----------------------------------------------------------------------------
		
//-----------------------------------------------------------------------------
		if (loop == 0)
		{
			tmp = tmp->pNext;
		}
		else;
	}
	
	//Lay gia tri root tra ve ham main
    BSTree->getRoot(pTree);  
	return pTree;
}
